package NewCoder;

public class BM72 {
    //空间复杂度O(1)
    public int FindGreatestSumOfSubArray(int[] array) {
        int n=array.length;
        int sum=0;
        int max=array[0];
        for(int i=0;i<array.length;i++){
            sum=Math.max(sum+array[i],array[i]);
            max=Math.max(sum,max);
        }
        return max;
    }

    //空间复杂度O(N)
//    public int FindGreatestSumOfSubArray(int[] array) {
//        int n=array.length;
//        int[] dp=new int[n];
//        int max=array[0];
//        dp[0]=array[0];
//        for(int i=1;i<dp.length;i++){
//            dp[i]=Math.max(dp[i-1]+array[i],array[i]);
//            max=Math.max(dp[i],max);
//        }
//        return max;
//    }
}
